home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / DiskUtil / Crunch / XPK / DOCS / HFMN.DOC < prev    next >
Text File  |  1994-11-26  |  5KB  |  124 lines
  1.  
  2.                                       HFMN
  3.                    A fast packing & unpacking dynamic huffman
  4.                                   Version 1.28
  5.                        Copyright © 1993/94 Martin Hauner
  6.  
  7.  
  8.  
  9.                                License/Disclaimer
  10.                                ------------------
  11.  
  12. This library may be freely distributed with the XPK compression package, as long
  13. as  it  is  kept  in its original, complete, and unmodified form.  It may not be
  14. distributed  by  itself  or  in  a  commercial  package  of  any kind without my
  15. permission.
  16.  
  17. This  program is distributed in the hope that it will be useful, but WITHOUT ANY
  18. WARRANTY;  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  19. PARTICULAR PURPOSE.
  20.  
  21.  
  22.                                   Description
  23.                                   -----------
  24.  
  25. This  XPK  sub-library  basically  uses  the same algorithm (dynamic huffman) as
  26. found  in  the xpkHUFF.library.  For more detailed information about the huffman
  27. algorithm, take a look into HUFF.doc from M.Zimmermann -- and skip the part that
  28. huffman  compression  &  decompression is pretty slow !.  In difference to HUFF,
  29. HFMN  is  FAST  on  compression and decompression and produces a slightly better
  30. output.   Although  the  basic  algorithm  is the same, it is entirely different
  31. implemented, therefore HFMN will not depack HUFF and HUFF not HFMN !
  32.  
  33.  
  34.      HFMN needs for private buffers (no xpkmaster.library buffers) 
  35.  
  36.                ·  7.5 Kbyte packing memory
  37.                ·  5   KByte unpacking memory
  38.  
  39.  
  40. Following  is  a  table  briefly  listing  some comparative statistics for HFMN.
  41. These  were  generated  by xBench on the standard XPK benchmark system (A3000/25
  42. with  SCRAM, using the AmigaVision executeable as data) and on A4000/40 (Booting
  43. without  Startup-Sequence, with Setpatch).  Note that memory needs don't include
  44. xpkmaster.library's buffers.
  45.  
  46.  
  47.         Method    Packing   Unpacking   Packing   Unpacking   Compression
  48.                   Memory     Memory      Speed      Speed        Ratio
  49.        ---------  -------   ---------   -------   ---------   -----------
  50.        HFMN.000+    7.5 K      5 K      223 K/s    209 K/s        24.7
  51.        HFMN.020+    7.5 K      5 K      259 K/s    209 K/s        24.7 
  52.  
  53.                          and now the same with A4000/40
  54.  
  55.         Method    Packing   Unpacking   Packing   Unpacking   Compression
  56.                   Memory     Memory      Speed      Speed        Ratio
  57.        ---------  -------   ---------   -------   ---------   -----------
  58.        HFMN.000+    7.5 K      5 K      537 K/s    569 K/s        24.7
  59.        HFMN.020+    7.5 K      5 K      592 K/s    569 K/s        24.7
  60.  
  61.  
  62.  
  63. How does it work?
  64.  
  65.  ·  First,  i use heapsort to create the huffman tree, which is most responsible
  66.     for  packing speed.
  67.     (heapsort is the second-best sort algorithm and is based upon binary trees)
  68.  
  69.  ·  Second,  (for decompression) i generate an (almost) optimal unpack code from
  70.     the huffman tree.
  71.  
  72.  ·  Third, i save the huffman tree recursivly.  That's why i need max.  320 byte
  73.     to save a complete huffman tree.
  74.  
  75.  
  76.  
  77.                                   020+ Version
  78.                                   ------------
  79.  
  80. I  have  experimented  with  020+  code  and rewrote the most used routines.  My
  81. huffman-code-translation-routine  :)  is  reduced  from  50  to 16 instructions,
  82. and achieves a noticable speedup. (hmm, i like bitfield instructions.:-)
  83.  
  84. .next        move.b    (a0)+,d2        ;incoming characters ( $00-$ff )
  85.         move.l    (a2,d2.w*4),d3        ;huffman code
  86.         move.b    3(a3,d2.w*4),d4        ;huffman codesize
  87.         bfins    d3,(a1){d5:d4}        ;store huffman code
  88.         add.l    d4,d5            ;bitoffset + last codesize
  89.         dbra    d7,.next
  90.  
  91. For decompression, the 020+ code produces no improvements.  But there were still
  92. some small optimizations possible, so decompression speed is improved too.
  93.  
  94.  
  95.  
  96.  
  97.                                 Version History
  98.                                 ---------------
  99.  
  100.           V 1.16 - first public version.
  101.           V 1.18 - 2 ways of decompression.
  102.           V 1.19 - bugfix: uncompressable data returns now XPKERR_EXPANSION
  103.                    instead of XPKERR_SMALLOUTBUF.
  104.  V 1.20 - V 1.27 - some experimental versions with 020+ code.
  105.           V 1.28 - extra library with 020+ code for compression.
  106.                  - improved 000+ decompression code.
  107.  
  108.  
  109.  
  110.  
  111.                                 Contact Address
  112.                                 ---------------
  113.  
  114.     any comments ?
  115.     email:
  116.     drizzt@trashcan.escape.de
  117.  
  118.     snail-mail:
  119.     Martin Hauner
  120.     Max-Born-Straße 5
  121.     38116 Braunschweig
  122.     Germany
  123.  
  124.